/*
题目：二叉搜索树和双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 */
public class TreeToDoublyList {
    Node prev = null;//记录刚经过的节点
    Node first = null;//记录双向链表的第一个节点
    public Node treeToDoublyList(Node root) {
        if (root == null)   return null;
        dfs(root);
        first.left = prev;
        prev.right = first;
        return first;
    }

    private void dfs(Node root) {
        if (root == null)   return ;
        dfs(root.left);
        if (prev != null) {
            prev.right = root;
        } else {
            first = root;
        }
        root.left = prev;
        prev = root;

        dfs(root.right);
    }
}
